package com.jiang.daily.Q3068;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/05/28 11:21
 */
class Solution {
    // 状态动态规划
    // public long maximumValueSum(int[] nums, int k, int[][] edges) {
    //     long f0 = 0, f1 = Long.MIN_VALUE;
    //     for (int x : nums) {
    //         long t = Math.max(f1 + x, f0 + (x ^ k));
    //         f0 = Math.max(f0 + x, f1 + (x ^ k));
    //         f1 = t;
    //     }
    //     return f0;
    // }

    // 贪心
    public long maximumValueSum(int[] nums, int k, int[][] edges) {
        long res = 0;

        // int[] diff = new int[nums.length];
        // for (int i = 0; i < nums.length; ++i) {
        //     res += nums[i];
        //     diff[i] = (nums[i] ^ k) - nums[i];
        // }
        // Arrays.sort(diff);
        // for (int i = diff.length - 1; i > 0 && diff[i] + diff[i - 1] >= 0; i -= 2) {
        //     res += diff[i] + diff[i - 1];
        // }
        // return res;

        boolean odd = true;
        int minNeg = Integer.MIN_VALUE; // 最小的负数
        int minPos = Integer.MAX_VALUE; // 最小的正数
        for (int i = 0; i < nums.length; ++i) {
            res += nums[i];
            int temp = (nums[i] ^ k) - nums[i];
            if (temp < 0) {
                minNeg = Math.max(minNeg, temp);
            } else {
                minPos = Math.min(minPos, temp);
                res += temp;
                odd = !odd;
            }
        }
        if (!odd) { // 奇数个正数
            if (minPos < -minNeg || minNeg == Integer.MIN_VALUE)  {
                res -= minPos; // 如果最小的正数的值小于最小的负数的值或者不存在最小负数的值，减去最小的正数
            } else {
                res += minNeg; // 否则，加上最小的负数
            }
        }
        return res;
    }
}
